package com.wj.sort;

/**
 * @author wen.jie
 * @date 2021/8/5 16:13
 */
public class Merge extends AbstractSort{

    private static Comparable[] assist;

//    public static void sort(Comparable[] a){
//        assist = new Comparable[a.length];
//        sort(a, 0, a.length - 1);
//    }

    public static void sort(Comparable[] a){
        int n = a.length;
        assist = new Comparable[n];
        for (int sz = 1; sz < n; sz = 2*sz) {
            for (int lo = 0; lo < n-sz; lo += 2*sz){
                merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, n-1));
            }
        }
    }

    /**
     * 排序：从lo到hi的元素
     * @author wen.jie
     * @date 2021/8/5 16:17
     */
    public static void sort(Comparable[] a, int lo, int hi){
        if(hi <= lo) return;
        int mid  = lo + (hi - lo) / 2;
        //两组分别排序
        sort(a, lo, mid);
        sort(a, mid + 1, hi);
        //两组中的数据进行合并
        merge(a, lo, mid, hi);
    }

    /**
     * 合并两个分组
     * @author wen.jie
     * @date 2021/8/5 16:21
     */
    public static void merge(Comparable[] a, int lo, int mid, int hi){
        //定义两个指针，对应着两个子数组
        int i = lo, j = mid + 1;
        //将所有元素先复制到临时数组中
        System.arraycopy(a, lo, assist, lo, hi + 1 - lo);
        //归并到a[lo...hi]
        for (int k = lo; k <= hi; k++) {
            if(i > mid)
                //左半边用尽,取右半边元素
                a[k] = assist[j++];
            else if (j > hi)
                //右半边用尽,取右半边元素
                a[k] = assist[i++];
            else if (less(assist[j], assist[i]))
                //右边比左边小,取右边元素
                a[k] = assist[j++];
            else
                //左边比右边小,取左边元素
                a[k] = assist[i++];
        }
    }

}
